/* 剑指 Offer II 091. 粉刷房子 */
/**
 * @param {number[][]} costs
 * @return {number}
 */

/* 
    动态规划:
    dp[i][j] 表示粉刷第0号房子到第i号房子被粉刷成第j种颜色时的
    最小成本{0 <= i < n, 0 <= j < 3}

    第i - 1 号房子只能被粉刷成另外两种颜色之一，当第i号房子分别被粉刷成
    3种颜色时,粉刷第0号房子到第i号房子的最小花费陈成本呢如下:
    dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i][0]
    dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + costs[i][1]
    dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + costs[i][2]

    合并状态转移方程
    dp[i][j] = min(dp[i-1][(j+1) % 3],dp[i-1][(j+2)%3]) + costs[i][j]
    结束时，dp[n-1] 中的最小值即为粉刷所有房子的最小花费成本

    当 i >= 1 时，由于dp[i]的计算只和dp[i-1]有关，因此可以使用滚动
    数组优化空间，将空间复杂度降到O(1)
*/
var minCost = function (costs) {
	const n = costs.length
	let dp = new Array(3).fill(0)
	for (let j = 0; j < 3; j++) {
		dp[j] = costs[0][j]
	}
	for (let i = 1; i < n; i++) {
		const dpNew = new Array(3).fill(0)
		for (let j = 0; j < 3; j++) {
			dpNew[j] = Math.min(dp[(j + 1) % 3], dp[(j + 2) % 3]) + costs[i][j]
		}
		dp = dpNew
	}
	return Math.min.apply(null, dp)
}

/* 
    [[6,4,13],[10,9,15],[14,15,11],[17,15,9],[7,10,13],[18,9,4],[5,20,12]]
*/
const ans = minCost([
	[20, 17, 16],
	[10, 14, 15],
	[7, 12, 20],
])
console.log('minCost :>>', ans)
